home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1997 January: Mac OS SDK / Dev.CD Jan 97 SDK2.toast / Development Kits (Disc 2) / OpenDoc Development Framework / ODFDev / ODF / Found / FWCollec / PRList.cpp < prev    next >
Encoding:
Text File  |  1996-09-17  |  16.8 KB  |  583 lines  |  [TEXT/MPS ]
  1. //========================================================================================
  2. //
  3. //    File:                PRList.cpp
  4. //    Release Version:    $ ODF 2 $
  5. //
  6. //    Copyright:    (c) 1993 - 1996 by Apple Computer, Inc., all rights reserved.
  7. //
  8. //========================================================================================
  9.  
  10. #include "FWFound.hpp"
  11.  
  12. #ifndef PRLIST_H
  13. #include "PRList.h"
  14. #endif
  15.  
  16. #ifndef FWDEBUG_H
  17. #include "FWDebug.h"
  18. #endif
  19.  
  20. #ifdef FW_BUILD_MAC
  21. #include <Errors.h>
  22. #endif
  23.  
  24. //========================================================================================
  25. // FW_CPrivLink
  26. //========================================================================================
  27.  
  28. #ifdef FW_BUILD_MAC
  29. #pragma segment fwcollec
  30. #endif
  31.  
  32. //========================================================================================
  33. // FW_CPrivLink
  34. //========================================================================================
  35. // Many of the simple link methods are inlines; see PRList.h for implementations.
  36.  
  37. //----------------------------------------------------------------------------------------
  38. // FW_CPrivLink::FW_CPrivLink
  39. //----------------------------------------------------------------------------------------
  40. // Constructor for FW_CPrivLink
  41.  
  42. FW_CPrivLink::FW_CPrivLink() :
  43.     fNext(NULL), 
  44.     fPrevious(NULL)                    
  45. { 
  46. }
  47.  
  48. //----------------------------------------------------------------------------------------
  49. // FW_CPrivLink::FW_CPrivLink
  50. //----------------------------------------------------------------------------------------
  51. // Constructor for FW_CPrivLink
  52.  
  53. FW_CPrivLink::FW_CPrivLink(FW_CPrivLink* next, FW_CPrivLink* previous) :                        
  54.     fNext(next),
  55.     fPrevious(previous)
  56. { 
  57. }
  58.  
  59. //----------------------------------------------------------------------------------------
  60. // FW_CPrivLink::FW_CPrivLink
  61. //----------------------------------------------------------------------------------------
  62. // Copy constructor for FW_CPrivLink
  63.  
  64. FW_CPrivLink::FW_CPrivLink(const FW_CPrivLink &link) :                            
  65.     fNext(link.fNext), 
  66.     fPrevious(link.fPrevious)
  67. { 
  68. }
  69.  
  70. //----------------------------------------------------------------------------------------
  71. // FW_CPrivLink::FW_CPrivLink
  72. //----------------------------------------------------------------------------------------
  73. // Destructor for FW_CPrivLink
  74.  
  75. FW_CPrivLink::~FW_CPrivLink()                                            
  76. {
  77. }
  78.  
  79. //----------------------------------------------------------------------------------------
  80. // FW_CPrivLink::Remove
  81. //----------------------------------------------------------------------------------------
  82. // Remove a link from its list (if any). DO NOT call this directly if there are
  83. // any iterators active on the list; use FW_CPrivLinkedList::Remove instead.
  84.  
  85. void    FW_CPrivLink::Remove( )
  86. {
  87.     if( fPrevious )
  88.         fPrevious->SetNext(fNext);
  89.     if( fNext )
  90.         fNext->SetPrevious(fPrevious);
  91.     fNext = NULL;
  92.     fPrevious = NULL;
  93. }
  94.  
  95. //----------------------------------------------------------------------------------------
  96. // FW_CPrivLink::AddBefore
  97. //----------------------------------------------------------------------------------------
  98. // Add a link to a list before another link. It must not already be on any list.
  99. // DO NOT call this directly if there are any iterators active on the list;
  100. // use FW_CPrivLinkedList::Remove instead.
  101.  
  102. void    FW_CPrivLink::AddBefore( FW_CPrivLink *link )
  103. {
  104.     FW_ASSERT(link!=NULL);
  105.     FW_ASSERT(fNext==NULL);
  106.     FW_ASSERT(fPrevious==NULL);
  107.     fNext = link;
  108.     fPrevious = link->GetPrevious();
  109.     fPrevious->SetNext(this);
  110.     fNext->SetPrevious(this);
  111. }
  112.  
  113. //----------------------------------------------------------------------------------------
  114. // FW_CPrivLink::AddAfter
  115. //
  116. // Add a link to a list after another link. It must not already be on any list.
  117. // DO NOT call this directly if there are any iterators active on the list;
  118. // use FW_CPrivLinkedList::Remove instead.
  119. //----------------------------------------------------------------------------------------
  120.  
  121. void    FW_CPrivLink::AddAfter( FW_CPrivLink *link )
  122. {
  123.     FW_ASSERT(link!=NULL);
  124.     FW_ASSERT(fNext==NULL);
  125.     FW_ASSERT(fPrevious==NULL);
  126.     fPrevious = link;
  127.     fNext = link->GetNext();
  128.     fPrevious->SetNext(this);
  129.     fNext->SetPrevious(this);
  130. }
  131.  
  132. //========================================================================================
  133. // Class FW_CPrivLinkedList
  134. //========================================================================================
  135.  
  136. //----------------------------------------------------------------------------------------
  137. // FW_CPrivLinkedList::FW_CPrivLinkedList
  138. //----------------------------------------------------------------------------------------
  139. // Constructor for FW_CPrivLinkedList
  140.  
  141. FW_CPrivLinkedList::FW_CPrivLinkedList()
  142.     :fSentinel(&fSentinel,&fSentinel),
  143.      fSeed(0),
  144.      fCount(0)
  145. {
  146. }
  147.  
  148. //----------------------------------------------------------------------------------------
  149. // FW_CPrivLinkedList::~FW_CPrivLinkedList
  150. //----------------------------------------------------------------------------------------
  151. // Destructor for FW_CPrivLinkedList
  152.  
  153. FW_CPrivLinkedList::~FW_CPrivLinkedList()
  154. {
  155.     // The list does NOT delete all its links!
  156. }
  157.  
  158. //----------------------------------------------------------------------------------------
  159. // FW_CPrivLinkedList::IsEmpty
  160. //----------------------------------------------------------------------------------------
  161.  
  162. FW_Boolean FW_CPrivLinkedList::IsEmpty() const
  163. {
  164.     return this->IsSentinel( fSentinel.GetNext() );
  165. }
  166.  
  167. //----------------------------------------------------------------------------------------
  168. // FW_CPrivLinkedList::Count
  169. //----------------------------------------------------------------------------------------
  170.  
  171. unsigned long FW_CPrivLinkedList::Count() const
  172. {
  173.     return fCount;
  174. /*
  175.     FW_CPrivLink* l = fSentinel.GetNext();
  176.     unsigned long count = 0;
  177.     while (this->NotSentinel(l))
  178.     {
  179.         count++;
  180.         l = l->GetNext();
  181.     }
  182.     return count;
  183. */
  184. }
  185.  
  186. //----------------------------------------------------------------------------------------
  187. // FW_CPrivLinkedList::Includes
  188. //----------------------------------------------------------------------------------------
  189. // Does the list include a particular link?
  190.  
  191. FW_Boolean FW_CPrivLinkedList::Includes( const FW_CPrivLink *link ) const
  192. {
  193.     FW_CPrivLink* l = fSentinel.GetNext();
  194.     while (this->NotSentinel(l))
  195.     {
  196.         if( l == link )
  197.             return TRUE;
  198.         else
  199.             l = l->GetNext();
  200.     }
  201.     return FALSE;
  202. }
  203.  
  204. //----------------------------------------------------------------------------------------
  205. // FW_CPrivLinkedList::DeleteAllLinks
  206. //----------------------------------------------------------------------------------------
  207.  
  208. void FW_CPrivLinkedList::DeleteAllLinks()
  209. {
  210.  
  211.     FW_CPrivLink* l = fSentinel.GetNext();
  212.     FW_CPrivLink* n = l;
  213.     while (this->NotSentinel(n))
  214.     {
  215.         n = l->GetNext();
  216.         delete l;    
  217.         l = n;
  218.     }
  219.     fSentinel.SetNext(&fSentinel);
  220.     fSentinel.SetPrevious(&fSentinel);
  221.     fSeed++;
  222.     fCount = 0;
  223. }
  224.  
  225. //----------------------------------------------------------------------------------------
  226. // FW_CPrivLinkedList::RemoveAll
  227. //----------------------------------------------------------------------------------------
  228.  
  229. void FW_CPrivLinkedList::RemoveAll()
  230. {
  231.     FW_CPrivLink* l = fSentinel.GetNext();
  232.     FW_CPrivLink* n = l;
  233.     while (this->NotSentinel(l))
  234.     {
  235.         n = l->GetNext();
  236.         l->SetNext(NULL);
  237.         l->SetPrevious(NULL);
  238.         l = n;
  239.     }
  240.     fSentinel.SetNext(&fSentinel);
  241.     fSentinel.SetPrevious(&fSentinel);
  242.     fSeed++;
  243.     fCount = 0;
  244. }
  245.  
  246. //----------------------------------------------------------------------------------------
  247. // FW_CPrivLinkedList::Remove
  248. //----------------------------------------------------------------------------------------
  249.  
  250. void FW_CPrivLinkedList::Remove(FW_CPrivLink* aLink)
  251. {
  252.     fSeed++;
  253.     fCount--;
  254.     aLink->Remove();
  255. }
  256.  
  257. //----------------------------------------------------------------------------------------
  258. // FW_CPrivLinkedList::RemoveFirst
  259. //----------------------------------------------------------------------------------------
  260.  
  261. FW_CPrivLink* FW_CPrivLinkedList::RemoveFirst()
  262. {
  263.     FW_CPrivLink* old = fSentinel.GetNext();
  264.     if (this->NotSentinel(old))
  265.     {
  266.         fSeed++;
  267.         fCount--;
  268.         old->Remove();
  269.         return old;
  270.     }
  271.     else
  272.     {
  273.         return NULL;
  274.     }
  275. }
  276.  
  277. //----------------------------------------------------------------------------------------
  278. // FW_CPrivLinkedList::RemoveLast
  279. //----------------------------------------------------------------------------------------
  280.  
  281. FW_CPrivLink* FW_CPrivLinkedList::RemoveLast()
  282. {
  283.     FW_CPrivLink* old = fSentinel.GetPrevious();
  284.     if (this->NotSentinel(old))
  285.     {
  286.         fSeed++;
  287.         fCount--;
  288.         old->Remove();
  289.         return old;
  290.     }
  291.     else
  292.     {
  293.         return NULL;
  294.     }
  295. }
  296.  
  297. //----------------------------------------------------------------------------------------
  298. // FW_CPrivLinkedList::AddFirst
  299. //----------------------------------------------------------------------------------------
  300.  
  301. void FW_CPrivLinkedList::AddFirst(FW_CPrivLink* link)
  302. {
  303.     link->AddAfter(this->GetSentinel());
  304.     fSeed++;
  305.     fCount++;
  306. }
  307.  
  308. //----------------------------------------------------------------------------------------
  309. // FW_CPrivLinkedList::AddLast( FW_CPrivLink )
  310. //----------------------------------------------------------------------------------------
  311.  
  312. void FW_CPrivLinkedList::AddLast(FW_CPrivLink* link)
  313. {
  314.     link->AddBefore(this->GetSentinel());
  315.     fSeed++;
  316.     fCount++;
  317. }
  318.  
  319. //----------------------------------------------------------------------------------------
  320. // FW_CPrivLinkedList::AddLast( FW_CPrivLinkedList )
  321. //----------------------------------------------------------------------------------------
  322. // Append contents of another list to my end. (Other list becomes empty.)
  323.  
  324. void FW_CPrivLinkedList::AddLast(FW_CPrivLinkedList &list)
  325. {
  326.     if( !list.IsEmpty() ) {
  327.         FW_CPrivLink *myLast = fSentinel.GetPrevious();
  328.         FW_CPrivLink *itsFirst = list.First();
  329.         myLast->SetNext(itsFirst);
  330.         itsFirst->SetPrevious(myLast);
  331.         
  332.         FW_CPrivLink *itsLast = list.Last();
  333.         itsLast->SetNext(this->GetSentinel());
  334.         fSentinel.SetPrevious(itsLast);
  335.         
  336.         list.fSentinel.SetNext(this->GetSentinel());
  337.         list.fSentinel.SetPrevious(this->GetSentinel());
  338.  
  339.         fSeed++;
  340.         fCount++;
  341.         list.fSeed++;
  342.     }
  343. }
  344.  
  345. //----------------------------------------------------------------------------------------
  346. // FW_CPrivLinkedList::AddLastUnique( FW_CPrivLinkedList )
  347. //----------------------------------------------------------------------------------------
  348. // Append contents of another list (w/o duplication) to my end.
  349.  
  350. void    FW_CPrivLinkedList::AddLastUnique(FW_CPrivLinkedList &list)
  351. {
  352.     for( FW_CPrivLink *link = fSentinel.GetNext(); this->NotSentinel(link); link=link->GetNext() )
  353.         if( list.Includes(link) )
  354.             list.Remove(link);
  355.     this->AddLast(list);
  356. }
  357.  
  358. //----------------------------------------------------------------------------------------
  359. // FW_CPrivLinkedList::AddBefore
  360. //----------------------------------------------------------------------------------------
  361.  
  362. void FW_CPrivLinkedList::AddBefore(FW_CPrivLink* existing, FW_CPrivLink* link)
  363. {
  364.     link->AddBefore(existing);
  365.     fSeed++;
  366.     fCount++;
  367. }
  368.  
  369. //----------------------------------------------------------------------------------------
  370. // FW_CPrivLinkedList::AddAfter
  371. //----------------------------------------------------------------------------------------
  372.  
  373. void FW_CPrivLinkedList::AddAfter(FW_CPrivLink* existing, FW_CPrivLink* link)
  374. {
  375.     link->AddAfter(existing);
  376.     fSeed++;
  377.     fCount++;
  378. }
  379.  
  380. //----------------------------------------------------------------------------------------
  381. // FW_CPrivLinkedList::After
  382. //----------------------------------------------------------------------------------------
  383.  
  384. FW_CPrivLink* FW_CPrivLinkedList::After(const FW_CPrivLink* link) const
  385. {
  386.     FW_CPrivLink *next = link->GetNext();
  387.     return (this->IsSentinel(next)) ? NULL : next;
  388. }
  389.  
  390. //----------------------------------------------------------------------------------------
  391. // FW_CPrivLinkedList::Before
  392. //----------------------------------------------------------------------------------------
  393.  
  394. FW_CPrivLink* FW_CPrivLinkedList::Before(const FW_CPrivLink* link) const
  395. {
  396.     FW_CPrivLink *prev = link->GetPrevious();
  397.     return this->IsSentinel(prev) ? NULL : prev;
  398. }
  399.  
  400. //----------------------------------------------------------------------------------------
  401. // FW_CPrivLinkedList::First
  402. //----------------------------------------------------------------------------------------
  403.  
  404. FW_CPrivLink* FW_CPrivLinkedList::First()  const
  405. {
  406.     return this->NotSentinel(fSentinel.GetNext()) ? fSentinel.GetNext() : (FW_CPrivLink*) NULL;
  407. }
  408.  
  409. //----------------------------------------------------------------------------------------
  410. // FW_CPrivLinkedList::Last
  411. //----------------------------------------------------------------------------------------
  412.  
  413. FW_CPrivLink* FW_CPrivLinkedList::Last() const
  414. {
  415.     return this->NotSentinel(fSentinel.GetPrevious()) ? fSentinel.GetPrevious() : (FW_CPrivLink*) NULL;
  416. }
  417.  
  418. //========================================================================================
  419. // Class FW_CPrivLinkedListIterator
  420. //========================================================================================
  421.  
  422. //----------------------------------------------------------------------------------------
  423. // FW_CPrivLinkedListIterator::FW_CPrivLinkedListIterator
  424. //----------------------------------------------------------------------------------------
  425. // Constructor for FW_CPrivLinkedListIterator
  426.  
  427. FW_CPrivLinkedListIterator::FW_CPrivLinkedListIterator(FW_CPrivLinkedList* list) :
  428.     fList(list),
  429.     fCurrent(NULL),
  430.     fNext(NULL),
  431.     fPrevious(NULL),
  432.     fSentinel(list ? &list->fSentinel : NULL),
  433.     fSeed(list ? fList->fSeed : 0)
  434. {
  435. }
  436.  
  437. //----------------------------------------------------------------------------------------
  438. // FW_CPrivLinkedListIterator::~FW_CPrivLinkedListIterator
  439. //----------------------------------------------------------------------------------------
  440. // Destructor for FW_CPrivLinkedListIterator
  441.  
  442. FW_CPrivLinkedListIterator::~FW_CPrivLinkedListIterator()
  443. {
  444. }
  445.  
  446. //----------------------------------------------------------------------------------------
  447. // FW_CPrivLinkedListIterator::First
  448. //----------------------------------------------------------------------------------------
  449.  
  450. FW_CPrivLink* FW_CPrivLinkedListIterator::First()
  451. {
  452.     if (fList == NULL)
  453.         return NULL;
  454.         
  455.     FW_ASSERT(fSeed == fList->fSeed);
  456.         
  457.     fCurrent = fList->First();
  458.     if (fCurrent == fSentinel)
  459.         fCurrent = NULL;
  460.     return fCurrent;
  461. }
  462.  
  463. //----------------------------------------------------------------------------------------
  464. // FW_CPrivLinkedListIterator::Next
  465. //----------------------------------------------------------------------------------------
  466.  
  467. FW_CPrivLink* FW_CPrivLinkedListIterator::Next()
  468. {
  469.     if (fList == NULL)
  470.         return NULL;
  471.  
  472.     FW_ASSERT(fSeed == fList->fSeed);
  473.  
  474.     if (fCurrent == NULL)
  475.     {
  476.         if ((fNext == NULL) && (fPrevious == NULL))    // Just starting out
  477.         {
  478.             return this->First();
  479.         }
  480.         else    // Just deleted
  481.         {
  482.             fCurrent = fNext;
  483.             fPrevious = NULL;
  484.             fNext = NULL;
  485.         }
  486.     }
  487.     else
  488.         fCurrent = fCurrent->GetNext();
  489.     
  490.     if (fCurrent == fSentinel)
  491.         fCurrent = NULL;
  492.     return fCurrent;
  493. }
  494.  
  495. //----------------------------------------------------------------------------------------
  496. // FW_CPrivLinkedListIterator::Last
  497. //----------------------------------------------------------------------------------------
  498.  
  499. FW_CPrivLink* FW_CPrivLinkedListIterator::Last()
  500. {
  501.     if (fList == NULL)
  502.         return NULL;
  503.  
  504.     FW_ASSERT(fSeed == fList->fSeed);
  505.  
  506.     fCurrent = fList->Last();
  507.     if (fCurrent == fSentinel)
  508.         fCurrent = NULL;
  509.     return fCurrent;
  510. }
  511.  
  512. //----------------------------------------------------------------------------------------
  513. // FW_CPrivLinkedListIterator::Previous
  514. //----------------------------------------------------------------------------------------
  515.  
  516. FW_CPrivLink* FW_CPrivLinkedListIterator::Previous()
  517. {
  518.     if (fList == NULL)
  519.         return NULL;
  520.  
  521.     FW_ASSERT(fSeed == fList->fSeed);
  522.  
  523.     if (fCurrent == NULL)
  524.     {
  525.         if ((fNext == NULL) && (fPrevious == NULL))    // Just starting out
  526.         {
  527.             return this->Last();
  528.         }
  529.         else    // Just deleted
  530.         {
  531.             fCurrent = fPrevious;
  532.             fPrevious = NULL;
  533.             fNext = NULL;
  534.         }
  535.     }
  536.     else
  537.         fCurrent = fCurrent->GetPrevious();
  538.  
  539.     if (fCurrent == fSentinel)
  540.         fCurrent = NULL;
  541.     return fCurrent;
  542. }
  543.  
  544. //----------------------------------------------------------------------------------------
  545. // FW_CPrivLinkedListIterator::Current
  546. //----------------------------------------------------------------------------------------
  547.  
  548. FW_CPrivLink* FW_CPrivLinkedListIterator::Current()
  549. {
  550.     return fCurrent;
  551. }
  552.  
  553. //----------------------------------------------------------------------------------------
  554. // FW_CPrivLinkedListIterator::IsNotComplete
  555. //----------------------------------------------------------------------------------------
  556.  
  557. FW_Boolean FW_CPrivLinkedListIterator::IsNotComplete()
  558. {
  559.     return (fCurrent != NULL);
  560. }
  561.  
  562. //----------------------------------------------------------------------------------------
  563. // FW_CPrivLinkedListIterator::RemoveCurrent
  564. //----------------------------------------------------------------------------------------
  565.  
  566. void  FW_CPrivLinkedListIterator::RemoveCurrent()
  567. {
  568.     if (fList == NULL)
  569.         return;
  570.  
  571.     FW_ASSERT(fSeed == fList->fSeed);
  572.          
  573.     if (fCurrent != NULL)
  574.     {
  575.         fNext = fCurrent->GetNext();
  576.         fPrevious = fCurrent->GetPrevious();
  577.             
  578.         fList->Remove(fCurrent);
  579.         fCurrent = NULL;
  580.         fSeed = fList->fSeed;
  581.     }
  582. }
  583.